Networks are a popular tool for representing elements in a system and theirinterconnectedness. Many observed networks can be viewed as only samples ofsome true underlying network. Such is frequently the case, for example, in themonitoring and study of massive, online social networks. We study the problemof how to estimate the degree distribution - an object of fundamental interest- of a true underlying network from its sampled network. In particular, we showthat this problem can be formulated as an inverse problem. Playing a key rolein this formulation is a matrix relating the expectation of our sampled degreedistribution to the true underlying degree distribution. Under many networksampling designs, this matrix can be defined entirely in terms of the designand is found to be ill-conditioned. As a result, our inverse problem frequentlyis ill-posed. Accordingly, we offer a constrained, penalized weightedleast-squares approach to solving this problem. A Monte Carlo variant ofStein's unbiased risk estimation (SURE) is used to select the penalizationparameter. We explore the behavior of our resulting estimator of network degreedistribution in simulation, using a variety of combinations of network modelsand sampling regimes. In addition, we demonstrate the ability of our method toaccurately reconstruct the degree distributions of various sub-communitieswithin online social networks corresponding to Friendster, Orkut andLiveJournal. Overall, our results show that the true degree distributions fromboth homogeneous and inhomogeneous networks can be recovered with substantiallygreater accuracy than reflected in the empirical degree distribution resultingfrom the original sampling.
展开▼
